COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00006 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a30.tex[154,phy] \today\hfill}

\bigskip
Given a DFA, to test strings, $x$ and $y$ for prefix equivalence.

The states $i$ and $j$ reached by reading $x$ and $y$ respectively
from the start state are $S\circ T↓x$ and $S\circ T↓y$. The relation
whose sole member is $\langle i,j\rangle$ is
$$U=(S\circ T↓x)\times (S\circ T↓y)\,,\quad\hbox{or}\quad
\widehat{T}↓x\circ I↓s\circ T↓y\,.$$
The relation of pairs $\langle k,l\rangle$ such that, for some string~$z$,
$iT↓zk$ and~$jT↓zl$, is given by repeatedly replacing $U$ by
$U\cup\bigcup↓{\sigma\in\Sigma}\widehat{T}↓{\sigma}\circ U\circ T↓{\sigma}$
until no change takes place ($n↑2$~steps suffice in the worst case).

If for all such pairs, $k$ and $l$ are both in~$F$, or neither in~$F$,
then $x\sim y$. That is,
$$x\sim y≡U\subseteq (F\times F\cup \bar{F}\times \bar{F})\,.$$
(This is testing that the original $U$ is a subset of the equivalence
relation on~$Q$.) The termination may be accelerated by stopping as soon
as a bad $\langle i,j\rangle$ appears in~$U$.

Given a DFA, to test strings $x$ and $y$ for infix equivalence.
The states $i$ and $j$ reached by reading $ux$ and~$uy$ respectively
are $S\circ T↓u\circ T↓x$ and $S\circ T↓u\circ T↓y$. The relation
of such pairs $\langle i,j\rangle$ is
$$U=\widehat{T}↓x\circ I↓{S\circ T↓{\Sigma↑{\ast}}}\circ T↓y\,,\quad\hbox{or}\quad
\widehat{T}↓x\circ I↓{S\circ T↓{\Sigma}↑{\ast}}\circ T↓y\,.$$
Proceed operating on $U$ as in the previous algorithm.

Define the vector function $\vec{T}$ in terms of relation~$T$ by
$\langle x↓1,x↓2,\ldots,x↓n\rangle\vec{T}=\langle x↓1T,x↓2T,\ldots,x↓nT\rangle$.
Then $\vec{T}↓{uv}=\vec{T}↓u\,\vec{T}↓v$.

If DFA $M$ is minimized, $x\sim y$ if $S\circ T↓x=S\circ T↓y$;
$x\approx y$ if $\vec{V}\,\vec{T}↓x=\vec{V}\,\vec{T}↓y$, where $V$~is
a~vector containing every state of~$M$.



\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft October 31, 1984

\bye